{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "#考点：二分查找\n",
    "def binSearch(ls, x):\n",
    "    l = 0\n",
    "    r = len(ls)-1\n",
    "    while(l <= r):\n",
    "        m = (l+r)//2\n",
    "        if(ls[m] == x):\n",
    "            return m\n",
    "        elif(x > ls[m]):\n",
    "            l = m + 1\n",
    "        else:\n",
    "            r = m - 1\n",
    "    return r #返回第一个小于x的下标\n",
    "class Solution:\n",
    "    #def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "    def searchMatrix(self, matrix, target: int) -> bool:\n",
    "        if matrix and matrix[0]:\n",
    "            r = binSearch([row[0] for row in matrix], target)\n",
    "            print(r)\n",
    "            if(r >= 0):\n",
    "                c = binSearch(matrix[r], target)\n",
    "                print(c)\n",
    "                if(c >= 0 and matrix[r][c] == target):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "0\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#测试\n",
    "matrix = [\n",
    "  [1,   3,  5,  7],\n",
    "  [10, 11, 16, 20],\n",
    "  [23, 30, 34, 50]\n",
    "]\n",
    "matrix = [[1]]\n",
    "target = 1\n",
    "a = Solution()\n",
    "print(a.searchMatrix(matrix, target))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = [x for x in range(100)]\n",
    "m = [1,   10,  23,  37]\n",
    "binSearch(m, 3)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
